package com.LeetCode.String;

import org.junit.Test;

/**
 * 最长回文子串
 */
public class LPD {
    public String longestPalindrome(String s){
        if(s == null || s.length() == 0)
            return "";
        int len = s.length();
        char[] chars = s.toCharArray();
        int[] range = new int[2];

        for(int i = 0; i<len; i++){
            i = findLongest(chars, i, range);
        }

        return s.substring(range[0] , range[1] + 1);
    }

    public int findLongest(char[] str, int low, int[] range){
        int high = low ;
        while(high < str.length - 1 && str[high+1] == str[low]){
            high++;
        }

        int ans = high;

        while(low > 0 && high < str.length - 1 && str[low-1] == str[high+1]){
            high++;
            low--;
        }

        if(high - low > range[1] - range[0]){
            range[0] = low;
            range[1] = high;
        }

        return ans;

    }


    @Test
    public void test(){
        String str = "babad";
        System.out.println(longestPalindrome(str));
    }
}
